/**
 * 880. 索引处的解码字符串
 * https://leetcode-cn.com/problems/decoded-string-at-index/
 */
public class Solutions_880 {
    public static void main(String[] args) {
//        String S = "leet2code3";
//        int K = 10;  // output: "o"

//        String S = "ha22";
//        int K = 5;  // output: "h"
//        int K = 6;  // output: "a"

//        String S = "a2345678999999999999999";
//        int K = 1;  // output: "a"

//        String S = "a2b3c4d5e6f7g8h9";
//        int K = 9;  // output: "b"

        String S = "ixm5xmgo78";
        int K = 711;  // output: "x"

        String result = decodeAtIndex(S, K);
        System.out.println(result);
    }

    public static String decodeAtIndex(String S, int K) {
        char[] arr = S.toCharArray();
        long size = 0;
        // 正向计算
        for (char c : arr) {
            if (c >= '2' && c <= '9') {
                size *= (c - '0');
            } else {
                size ++;
            }
        }
        // 逆向计算
        for (int i = arr.length - 1; i >= 0; i--) {
            // 关键：K 随着 size 变化
            K %= size;
            if (arr[i] >= '2' && arr[i] <= '9') {
                // 是数字
                size /= (arr[i] - '0');
            } else {
                if (K == 0) {
                    // 找到第 K 个字符
                    return Character.toString(arr[i]);
                }
                size --;
            }
        }
        return "";
    }
}
